#!/usr/bin/python
# coding=utf-8
import os
from ConfigParser import ConfigParser


def main():
    CONFIGFILE = "pyLibs/config.txt"
    config = ConfigParser()
    config.read(CONFIGFILE)

    starts = dict()
    ends = dict()
    sources = []

    dict_construct(config, starts, ends, sources)

    f = open(config.get('Filename', 'output1'), 'w')
    for s in sources:
        for e in starts[s]:
            process(f, starts, [s], e)
    f.close()
    
    #os.system(
    #    "split -l 100000 " + config.get('Filename', 'output1') + ' ' + config.get('Filename', 'dir') + "/" + config.get(
    #        'Filename', 'prefix'))
    #try:
    #    os.system("rm " + config.get('Filename', 'output1'))
    #finally:
    #    pass


def dict_construct(config, starts, ends, sources):
    for line in open(config.get('Filename', 'input')):
        line = line.strip().split(' ')
        startpoint = line[0]
        endpoint = line[1]
        if startpoint == endpoint:
            continue
        else:
            if startpoint in starts:
                starts[startpoint].append(endpoint)
            else:
                starts[startpoint] = [endpoint]

            if endpoint in ends:
                ends[endpoint].append(startpoint)
            else:
                ends[endpoint] = [startpoint]

    s = starts.keys()
    e = ends.keys()
    for source in s:
        if source not in e:
            sources.append(source)


def process(f, starts, path, v):
    # print 'now process:',path,v
    if v in path:
        # 每条路径的起点不可能在环上，因此index不为0
        # print path,v
        next = []
        for index, val in enumerate(path):
            if val == v:
                next.append(path[index + 1])
        loop = 1
    else:
        loop = 0
    if v in starts:
        for e in starts[v]:
            if loop and e in next:
                if len(starts[v]) == 1:
                    f.write(' '.join(path) + ' -1 \n')
                else:
                    continue
            else:
                path.append(v)
                process(f, starts, path, e)
                path.pop()
    else:  # 如果v是路径末端
        path.append(v)
        f.write(' '.join(path) + ' -1 \n')
        path.pop()


if __name__ == '__main__':
    main()
